#include<iostream>
#include<vector>
using namespace std;
/*
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
解题思路：
与求子序列的题目类似,dp[i][j]表示s中以下标为i-1含有t中以j-1为结尾的元素个数，
所以有if(s1[i-1]==s2[j-1])dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
与之前的题目不一样，这里假设s=bagg,t=bag,当i=4，j=3时，有s1[i-1]==s2[j-1]，此时s要进行删除元素再次与t进行比较,
所以dp[i][j] = dp[i-1][j-1](s中下标以i-2结尾的含有t下标以j-2为结尾的元素的个数)
+dp[i-1][j](s下标以i-1为结尾的含有t下标以j-1为结尾的元素的个数)
else 
dp[i][j] = dp[i-1][j]
如何进行初始化呢，dp[i][0]表示s中以i-1为结尾的含有下标以-1结尾的t的个数，dp[i][0] = 1;
dp[0][j]表示s中以-1结尾的含有下标以j-1结尾的t的个数,dp[0][j] = 0;
dp[0][0]=1;
*/
int dp(string s1,string s2)
{
    //创建dp数组
    vector<vector<int>> dp(s1.size()+1,vector<int>(s2.size()+1));
    for(int i=0;i<=s1.size();i++)
        dp[i][0] = 1;
    //遍历dp数组
    for(int i=1;i<=s1.size();i++)
    {
        for(int j=1;j<=s2.size();j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
            }
            else 
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[s1.size()][s2.size()];
}

int main()
{
    cout<<"enter s1:"<<endl;
    string s1,s2;
    cin>>s1;
    cout<<"enter s2:"<<endl;
    cin>>s2;
    cout<<dp(s1,s2);
    return 0;
}